package org.example.arithmatic;

/**
 * 选择排序
 * 核心思想：
 * ‌遍历未排序部分‌，找到最小元素的索引。
 * 将最小元素与未排序部分的‌第一个元素交换‌。
 * 重复上述过程，直到所有元素有序。
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        selectionSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // 输出: [2, 3, 4, 5, 8]
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 遍历所有未排序位置
        for (int i = 0; i < n - 1; i++) {
            // 假设当前i是未排序部分的最小值索引
            int minIdx = i;

            // 在比对部分中查找实际最小值索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j; // 更新最小值索引
                }
            }

            // 将最小值交换到已排序部分的末尾
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

